翻訳と辞書 Words near each other ・ Average rectified value ・ Average revenue per user ・ Average Rock 'n' Roller ・ Average selling price ・ Average treatment effect ・ Average true range ・ Average variable cost ・ Average weekly earnings ・ Average White Band ・ Average Wholesale Price ・ Average worker's wage ・ Average-case complexity ・ Averaged Lagrangian ・ Averaged one-dependence estimators ・ Averageness ・ Averaging argument ・ Averan ・ Averara ・ Averardo de' Medici ・ Averasboro ・ Averasboro Battlefield and Museum ・ Averasboro Battlefield Historic District ・ Averasboro Township, Harnett County, North Carolina ・ Averatec ・ Averau ・ Averbis ・ Averbode ・ Averbode (publisher) ・ Averbode Abbey ・ Avercamp Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Averaging argument ： ウィキペディア英語版 Averaging argument In computational complexity theory and cryptography, averaging argument is a standard argument for proving theorems. It usually allows us to convert probabilistic polynomial-time algorithms into non-uniform polynomial-size circuits. == Example == To simplify, let's first consider an example. Example: If every person likes at least 1/3 of the books in a library, then, there exists a book, which at least 1/3 of people liked it. Proof: Suppose there are $N$ people and B books. Each person likes at least $B/3$ of the books. Let people leave a mark on the book they like. Then, there will be at least $M=(NB)/3$ marks. The averaging argument claims that there exists a book with at least $N/3$ marks on it. Assume, to the contradiction, that no such book exists. Then, every book has fewer than $N/3$ marks. However, since there are $B$ books, the total number of marks will be fewer than $(NB)/3$, contradicting the fact that there are at least $M$ marks. $\backslash scriptstyle\backslash blacksquare$ 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Averaging argument」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.